Come possiamo descrivere matematicamente i fili invisibili che collegano la società? Sia esso il Numeri di Bacon che collegano Bela Lugosi agli iconici attori di Hollywood o Grafici di Similarità che raggruppano punti dati in base alla vicinanza, Teoria dei Grafi fornisce il linguaggio formale $G = (V, E)$ per modellare questi universi discreti.
1. L'Anatomia dei Grafi
Nel suo nucleo, un grafo è composto da un insieme di vertici ($V$) e un insieme di archi ($E$). Tuttavia, le regole di utilizzo variano in base alla struttura:
- Grafo semplice: La forma più elegante; vieta cicli (archi che collegano un vertice a se stesso) e archi paralleli (archi ridondanti tra gli stessi due punti).
- Multigrafo: Permette cicli e archi paralleli, spesso utilizzato per modellare diversi tipi di interazioni (ad esempio testo rispetto a chiamata) tra gli stessi due nodi.
- Vertice isolato: Un vertice $v$ è isolato se nessun arco è incidente su di esso, rappresentando un oggetto senza relazioni nell'insieme corrente.
Nella scienza dei dati, spesso usiamo una Funzione di Dissimilarità per costruire grafi:
$$s(v, w) = |p_1 - q_1| + |p_2 - q_2| + |p_3 - q_3|$$
Disegniamo un arco tra $v$ e $w$ solo se $s(v, w)$ è inferiore a un certo valore soglia, creando efficacemente una rete di "vicini".
2. Cammini, Connettività e Componenti
Un cammino è una sequenza di vertici e archi. Se un cammino visita ogni vertice al massimo una volta, si dice cammino semplice. La connettività è il battito del grafo:
- Grafo connesso: Esiste un cammino tra ogni ogni coppia di vertici nel grafo.
- Componenti: Se un grafo non è connesso, si spezza in parti disgiunte chiamate componenti. Ogni componente è un sottografo connesso massimale.
3. Sottografi: L'Architettura degli Sottoinsiemi
Un sottografo $G' = (V', E')$ è un sottoinsieme di un grafo $G$ tale che ogni vertice in $V'$ esista in $V$, e ogni arco in $E'$ collega vertici presenti in $V'$. Identificare i sottografi è fondamentale per rilevare schemi locali all'interno di reti globali.